package demo.practice.bfs;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class P279 {

    public int numSquares(int n) {

        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

        queue.add(n);
        //visited.add(n);
        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                Integer top = queue.poll();
                int maxSqu = (int) Math.pow(top, 0.5);
                for (int i = maxSqu; i >= 0; i--) {
                    if (top == i * i) {
                        return level + 1;
                    } else {
                        int remain = top - (i * i);
                        if (!visited.contains(remain)) {
                            queue.add(remain);
                        }
                    }
                }
                size--;
                visited.add(top);
            }
            level++;
        }

        return -1;
    }

}
